Stateful bulk processing for incremental analytics.
This work addresses the need for stateful dataflow programs that can rapidly sift through huge, evolving data sets. These data-intensive applications perform complex multi-step computations over successive generations of data inflows, such as weekly web crawls, daily image/video uploads, log files, and growing social networks. While programmers may simply re-run the entire dataflow when new data arrives, this is grossly inefficient, increasing result latency and squandering hardware resources and energy. Alternatively, programmers may use prior results to incrementally incorporate the changes. However, current large-scale data processing tools, such as Map-Reduce or Dryad, limit how programmers incorporate and use state in data-parallel programs. Straightforward approaches to incorporating state can result in custom, fragile code and disappointing performance. This work presents a generalized architecture for continuous bulk processing (CBP) that raises the level of abstraction for building incremental applications. At its core is a flexible, groupwise processing operator that takes state as an explicit input. Unifying stateful programming with a data-parallel operator affords several fundamental opportunities for minimizing the movement of data in the underlying processing system. As case studies, we show how one can use a small set of flexible dataflow primitives to perform web analytics and mine large-scale, evolving graphs in an incremental fashion. Experiments with our prototype using real-world data indicate significant data movement and running time reductions relative to current practice. For example, incrementally computing PageRank using CBP can reduce data movement by 46 % and cut running time in half.
Web Crawling.

Interactive Analysis of Web%2DScale Data.
We consider how to support interactive querying over webscale data. The basic approach is to view querying as a two-phase activity: first supply a query template, and later supply specific instantiations of the template. Interactive responsiveness is offered in the second phase only. While instances of this problem have been studied in the past, e.g., OLAP and web search, we pursue a more general formulation. Our aim is to build a general two-phase query system. 1.
Generating example data for dataflow programs.
While developing data-centric programs, users often run (portions of) their programs over real data, to see how they behave and what the output looks like. Doing so makes it easier to formulate, understand and compose programs correctly, compared with examination of program logic alone. For large input data sets, these experimental runs can be time-consuming and inefficient. Unfortunately, sampling the input data does not always work well, because selective operations such as filter and join can lead to empty results over sampled inputs, and unless certain indexes are present there is no way to generate biased samples efficiently. Consequently new methods are needed for generating example input data for data-centric programs. We focus on an important category of data-centric programs, dataflow programs, which are best illustrated by displaying the series of intermediate data tables that occur between each pair of operations. We introduce and study the problem of generating example intermediate data for dataflow programs, in a manner that illustrates the semantics of the operators while keeping the example data small. We identify two major obstacles that impede naive approaches, namely (1) highly selective operators and (2) noninvertible operators, and offer techniques for dealing with these obstacles. Our techniques perform well on real dataflow programs used at Yahoo! for web analytics.
Building a HighLevel Dataflow System on top of MapReduce The Pig Experience.
Increasingly, organizations capture, transform and analyze enormous data sets. Prominent examples include internet companies and e-science. The Map-Reduce scalable dataflow paradigm has become popular for these applications. Its simple, explicit dataflow programming model is favored by some over the traditional high-level declarative approach: SQL. On the other hand, the extreme simplicity of Map-Reduce leads to much low-level hacking to deal with the many-step, branching dataflows that arise in practice. Moreover, users must repeatedly code standard operations such as join by hand. These practices waste time, introduce bugs, harm readability, and impede optimizations. Pig is a high-level dataflow system that aims at a sweet spot between SQL and Map-Reduce. Pig offers SQL-style high-level data manipulation constructs, which can be assembled in an explicit dataflow and interleaved with custom Map- and Reduce-style functions or executables. Pig programs are compiled into sequences of Map-Reduce jobs, and executed in the Hadoop Map-Reduce environment. Both Pig and Hadoop are open-source projects administered by the Apache Software Foundation. This paper describes the challenges we faced in developing Pig, and reports performance comparisons between Pig execution and raw Map-Reduce execution. 1.
Parallel Evaluation of Composite Aggregate Queries.
Abstract — Aggregate measures summarizing subsets of data are valuable in exploratory analysis and decision support, especially when dependent aggregations can be easily specified and computed. A novel class of queries, called composite subset measures, was previously introduced to allow correlated aggregate queries to be easily expressed. This paper considers how to evaluate composite subset measure queries using a large distributed system. We describe a cross-node data redistribution strategy that takes into account the nested structure of a given query. The main idea is to group data into blocks in “cube space”, such that aggregations can be generated locally within each block, leveraging previously proposed optimizations per-block. The partitioning scheme allows overlap among blocks so that sliding window aggregation can be handled. Furthermore, it also guarantees that the final answer is the union of local results with no duplication and there is no need for the expensive data combination step. We identify the most important partitioning parameters and propose an optimization algorithm. We also demonstrate effectiveness of the optimizer to minimize the query response time. I.
Parallel Evaluation of Composite Aggregate Queries.
Abstract — Aggregate measures summarizing subsets of data are valuable in exploratory analysis and decision support, especially when dependent aggregations can be easily specified and computed. A novel class of queries, called composite subset measures, was previously introduced to allow correlated aggregate queries to be easily expressed. This paper considers how to evaluate composite subset measure queries using a large distributed system. We describe a cross-node data redistribution strategy that takes into account the nested structure of a given query. The main idea is to group data into blocks in “cube space”, such that aggregations can be generated locally within each block, leveraging previously proposed optimizations per-block. The partitioning scheme allows overlap among blocks so that sliding window aggregation can be handled. Furthermore, it also guarantees that the final answer is the union of local results with no duplication and there is no need for the expensive data combination step. We identify the most important partitioning parameters and propose an optimization algorithm. We also demonstrate effectiveness of the optimizer to minimize the query response time. I.
Pig latin a not%2Dso%2Dforeign language for data processing.
There is a growing need for ad-hoc analysis of extremely large data sets, especially at internet companies where innovation critically depends on being able to analyze terabytes of data collected every day. Parallel database products, e.g., Teradata, offer a solution, but are usually prohibitively expensive at this scale. Besides, many of the people who analyze this data are entrenched procedural programmers, who find the declarative, SQL style to be unnatural. The success of the more procedural map-reduce programming model, and its associated scalable implementations on commodity hardware, is evidence of the above. However, the map-reduce paradigm is too low-level and rigid, and leads to a great deal of custom user code that is hard to maintain, and reuse. We describe a new language called Pig Latin that we have designed to fit in a sweet spot between the declarative style of SQL, and the low-level, procedural style of map-reduce. The accompanying system, Pig, is fully implemented, and compiles Pig Latin into physical plans that are executed over Hadoop, an open-source, map-reduce implementation. We give a few examples of how engineers at Yahoo! are using Pig to dramatically reduce the time required for the development and execution of their data analysis tasks, compared to using Hadoop directly. We also report on a novel debugging environment that comes integrated with Pig, that can lead to even higher productivity gains. Pig is an open-source, Apache-incubator project, and available for general use. 1.
Automatic Optimization of Parallel Dataflow Programs.
Large-scale parallel dataflow systems, e.g., Dryad and Map-Reduce, have attracted significant attention recently. High-level dataflow languages such as Pig Latin and Sawzall are being layered on top of these systems, to enable faster program development and more maintainable code. These languages engender greater transparency in program structure, and open up opportunities for automatic optimization. This paper proposes a set of optimization strategies for this context, drawing on and extending techniques from the database community. 1
Crawl ordering by search impact.
We study how to prioritize the fetching of new pages under the objective of maximizing the quality of search results. In particular, our objective is to fetch new pages that have the most impact, where the impact of a page is equal to the number of times the page appears in the top K search results for queries, for some constant K, e.g., K = 10. Since the impact of a page depends on its relevance score for queries, which in turn depends on the page content, the main difficulty lies in estimating the impact of the page before actually fetching it. Hence, impact must be estimated based on the limited information that is available prior to fetching page content, e.g., the URL string, number of in-links, referring anchortext. We formally characterize this problem and study its hardness. We leverage our formalism to design a new impactdriven crawling policy, and demonstrate its effectiveness using real world data. Our technique ensures that the crawler acquires content relevant to “tail topics ” that are obscure but of interest to some users, rather than just redundantly accumulating content on popular topics.
Recrawl scheduling based on information longevity.
It is crucial for a web crawler to distinguish between ephemeral and persistent content. Ephemeral content (e.g., quote of the day) is usually not worth crawling, because by the time it reaches the index it is no longer representative of the web page from which it was acquired. On the other hand, content that persists across multiple page updates (e.g., recent blog postings) may be worth acquiring, because it matches the page’s true content for a sustained period of time. In this paper we characterize the longevity of information found on the web, via both empirical measurements and a generative model that coincides with these measurements. We then develop new recrawl scheduling policies that take longevity into account. As we show via experiments over real web data, our policies obtain better freshness at lower cost, compared with previous approaches.
Scalable query result caching for web applications.
The backend database system is often the performance bottleneck when running web applications. A common approach to scale the database component is query result caching, but it faces the challenge of maintaining a high cache hit rate while efficiently ensuring cache consistency as the database is updated. In this paper we introduce Ferdinand, the first proxy-based cooperative query result cache with fully distributed consistency management. To maintain a high cache hit rate, Ferdinand uses both a local query result cache on each proxy server and a distributed cache. Consistency management is implemented with a highly scalable publish / subscribe system. We implement a fully functioning Ferdinand prototype and evaluate its performance compared to several alternative query-caching approaches, showing that our high cache hit rate and consistency management are both critical for Ferdinand’s performance gains over existing systems.  
Relaxation in text search using taxonomies.
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top k results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm. 1.
Scheduling shared scans of large data files.
We study how best to schedule scans of large data files, in the presence of many simultaneous requests to a common set of files. The objective is to maximize the overall rate of processing these files, by sharing scans of the same file as aggressively as possible, without imposing undue wait time on individual jobs. This scheduling problem arises in batch data processing environments such as Map-Reduce systems, some of which handle tens of thousands of processing requests daily, over a shared set of files. As we demonstrate, conventional scheduling techniques such as shortest-job-first do not perform well in the presence of cross-job sharing opportunities. We derive a new family of scheduling policies specifically targeted to sharable workloads. Our scheduling policies revolve around the notion that, all else being equal, it is good to schedule nonsharable scans ahead of ones that can share IO work with future jobs, if the arrival rate of sharable future jobs is expected to be high. We evaluate our policies via simulation over varied synthetic and real workloads, and demonstrate significant performance gains compared with conventional scheduling approaches. 1.
Invalidation Clues for Database Scalability Services.
For their scalability needs, data-intensive Web applications can use a Database Scalability Service (DBSS), which caches applications ’ query results and answers queries on their behalf. One way for applications to address their security/privacy concerns when using a DBSS is to encrypt all data that passes through the DBSS. Doing so, however, causes the DBSS to invalidate large regions of its cache when data updates occur. To invalidate more precisely, the DBSS needs help in order to know which results to invalidate; such help inevitably reveals some properties about the data. In this paper, we present invalidation clues, a general technique that enables applications to reveal little data to the DBSS, yet limit the number of unnecessary invalidations. Compared with previous approaches, invalidation clues provide applications significantly improved tradeoffs between security/privacy and scalability. Our experiments using three Web application benchmarks, on a prototype DBSS we have built, confirm that invalidation clues are indeed a low-overhead, effective, and general technique for applications to balance their privacy and scalability needs. 1.
Configurations a model for distributed data storage.

Navigationaided retrieval.
Users searching for information in hypermedia environments often perform querying followed by manual navigation. Yet, the conventional text/hypertext retrieval paradigm does not take post-query navigation into account. This paper proposes a new retrieval paradigm, called navigation-aided retrieval  (NAR), which treats both querying and navigation as first-class activities. In the NAR paradigm, querying is seen as a means to identify starting points for navigation, and navigation is guided based on information supplied in the query. NAR is a generalization of the conventional probabilistic information retrieval paradigm, which implicitly assumes no navigation takes place. This paper
The discoverability of the web.

Computing shortest paths with uncertainty.
We consider the problem of estimating the length of a shortest path in a DAG whose edge  lengths are known only approximately but can be determined exactly at a cost. We obtain both  positive and negative results on both the exact problem and its approximation.  1 
Handling Advertisements of Unknown Quality in Search Advertising.

Simultaneous scalability and security for data%2Dintensive web applications.
For Web applications in which the database component is the bottleneck, scalability can be provided by a third-party Database Scalability Service Provider (DSSP) that caches application data and supplies query answers on behalf of the application. Cost-effective DSSPs will need to cache data from many applications, inevitably raising concerns about security. However, if all data passing through a DSSP is encrypted to enhance security, then data updates trigger invalidation of large regions of cache. Consequently, achieving good scalability becomes virtually impossible. There is a tradeoff between security and scalability, which requires careful consideration. In this paper we study the security-scalability tradeoff, both formally and empirically. We begin by providing a method for statically identifying segments of the database that can be encrypted without impacting scalability. Experiments over a prototype DSSP system show the effectiveness of our static analysis method—for all three realistic benchmark applications that we study, our method enables a significant fraction of the database to be encrypted without impacting scalability. Moreover, most of the data that can be encrypted without impacting scalability is of the type that application designers will want to encrypt, all other things being equal. Based on our static analysis method, we propose a new scalability-conscious security design methodology that features: (a) compulsory encryption of highly sensitive data like credit card information, and (b) encryption of data for which encryption does not impair scalability. As a result, the security-scalability tradeoff needs to be considered only over data for which encryption impacts scalability, thus greatly simplifying the task of managing the tradeoff. 1.
A Scalability Service for Dynamic Web Applications.

Finding %28Recently%29 Frequent Items in Distributed Data Streams.
We consider the problem of maintaining frequency counts for items occurring frequently in the union of multiple distributed data streams. Naïve methods of combining approximate frequency counts from multiple nodes tend to result in excessively large data structures that are costly to transfer among nodes. To minimize communication requirements, the degree of precision maintained by each node while counting item frequencies must be managed carefully. We introduce the concept of a precision gradient for managing precision when nodes are arranged in a hierarchical communication structure. We then study the optimization problem of how to set the precision gradient so as to minimize communication, and provide optimal solutions that minimize worst-case communication load over all possible inputs. We then introduce a variant designed to perform well in practice, with input data that does not conform to worst-case characteristics. We verify the effectiveness of our approach empirically using real-world data, and show that our methods incur substantially less communication than naïve approaches while providing the same error guarantees on answers. 1.
Shuffling a Stacked Deck The Case for Partially Randomized Ranking of Search Engine Results.
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is closely correlated with quality, a more elusive concept that is difficult to measure directly. Unfortunately, the correlation between popularity and quality is very weak for newly-created pages that have yet to receive many visits and/or in-links. Worse, since discovery of new content is largely done by querying search engines, and because users usually focus their attention on the top few results, newly-created but high-quality pages are effectively “shut out, ” and it can take a very long time before they become popular. We propose a simple and elegant solution to this problem: the introduction of a controlled amount of randomness into search result ranking methods. Doing so offers new pages a chance to prove their worth, although clearly using too much randomness will degrade result quality and annul any benefits achieved. Hence there is a tradeoff between exploration to estimate the quality of new pages and exploitation of pages already known to be of high quality. We study this tradeoff both analytically and via simulation, in the context of an economic objective function based on aggregate result quality amortized over time. We show that a modest amount of randomness leads to improved search results. 1
Shuffling a Stacked Deck The Case for Partially Randomized Ranking of Search Engine Results
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is closely correlated with quality, a more elusive concept that is difficult to measure directly. Unfortunately, the correlation between popularity and quality is very weak for newly-created pages that have yet to receive many visits and/or in-links. Worse, since discovery of new content is largely done by querying search engines, and because users usually focus their attention on the top few results, newly-created but high-quality pages are effectively “shut out, ” and it can take a very long time before they become popular. We propose a simple and elegant solution to this problem: the introduction of a controlled amount of randomness into search result ranking methods. Doing so offers new pages a chance to prove their worth, although clearly using too much randomness will degrade result quality and annul any benefits achieved. Hence there is a tradeoff between exploration to estimate the quality of new pages and exploitation of pages already known to be of high quality. We study this tradeoff both analytically and via simulation, in the context of an economic objective function based on aggregate result quality amortized over time. We show that a modest amount of randomness leads to improved search results. 1
User%2Dcentric Web crawling.
Search engines are the primary gateways of information access on the Web today. Behind the scenes, search engines crawl the Web to populate a local indexed repository of Web pages, used to answer user search queries. In an aggregate sense, the Web is very dynamic, causing any repository of Web pages to become out of date over time, which in turn causes query answer quality to degrade. Given the considerable size, dynamicity, and degree of autonomy of the Web as a whole, it is not feasible for a search engine to maintain its repository exactly synchronized with the Web. In this paper we study how to schedule Web pages for selective (re)downloading into a search engine repository. The scheduling objective is to maximize the quality of the user experience for those who query the search engine. We begin with a quantitative characterization of the way in which the discrepancy between the content of the repository and the current content of the live Web impacts the quality of the user experience. This characterization leads to a usercentric metric of the quality of a search engine’s local repository. We use this metric to derive a policy for scheduling Web page (re)downloading that is driven by search engine usage and free of exterior tuning parameters. We then focus on the important subproblem of scheduling refreshing of Web pages already present in the repository, and show how to compute the priorities efficiently. We provide extensive empirical comparisons of our user-centric method against prior Web page refresh strategies, using real Web data. Our results demonstrate that our method requires far fewer resources to maintain same search engine quality level for users, leaving substantially more resources available for incorporating new Web pages into the search repository.
Shuffling a Stacked Deck The Case for Partially Randomized Ranking of Search Engine Results
In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is closely correlated with quality, a more elusive concept that is difficult to measure directly. Unfortunately, the correlation between popularity and quality is very weak for newly-created pages that have yet to receive many visits and/or in-links. Worse, since discovery of new content is largely done by querying search engines, and because users usually focus their attention on the top few results, newly-created but high-quality pages are effectively “shut out, ” and it can take a very long time before they become popular. We propose a simple and elegant solution to this problem: the introduction of a controlled amount of randomness into search result ranking methods. Doing so offers new pages a chance to prove their worth, although clearly using too much randomness will degrade result quality and annul any benefits achieved. Hence there is a tradeoff between exploration to estimate the quality of new pages and exploitation of pages already known to be of high quality. We study this tradeoff both analytically and via simulation, in the context of an economic objective function based on aggregate result quality amortized over time. We show that a modest amount of randomness leads to improved search results. 1
Efficient Monitoring and Querying of Distributed
It is increasingly common for an application&#039;s data to reside at multiple disparate locations, while the application  requires centralized access to its data. A simple solution is to replicate all relevant data at a central point,  forwarding updates from master copies to replicas without any special processing or filtering along the way. This  scheme maintains up-to-date centralized data, but incurs signficant communication overhead when the data is  highly dynamic, because the volume of updates is large. If communication resources are precious, communication  can be reduced by prioritizing and filtering updates inside the network, at or near the data sources. When updates  are dropped, the replicas become approximate rather than exact. Fortunately, many real-world applications involving  distributed, dynamic data can tolerate approximate data values to some extent, so approximate replication  is an important technique for balancing replica precision against the communication resources to achieve it.
WIC A General%2DPurpose Algorithm for Monitoring Web Information Sources.
The Web is becoming a universal information dissemination  medium, due to a number of factors  including its support for content dynamicity. A  growing number of Web information providers  post near real-time updates in domains such as  auctions, stock markets, bulletin boards, news,  weather, roadway conditions, sports scores, etc.
What%27s new on the web%3F the evolution of the web from a search engine perspective.
We seek to gain improved insight into how Web search engines should cope with the evolving Web, in an attempt to provide users with the most up-to-date results possible. For this purpose we collected weekly snapshots of some 150 Web sites over the course of one year, and measured the evolution of content and link structure. Our measurements focus on aspects of potential interest to search engine designers: the evolution of link structure over time, the rate of creation of new pages and new distinct content on the Web, and the rate of change of the content of existing pages under search-centric measures of degree of change.
Query Processing
Hardware for sensor nodes that combine physical sensors, actuators, embedded processors, and communication components has advanced significantly over the last decade, and made the large-scale deployment of such sensors a reality. Applications range from monitoring applications such as inventory maintenance over health care to military applications.
Distributed Top%2DK Monitoring.
The querying and analysis of data streams has been a topic of much recent interest, motivated by applications from the fields of networking, web usage analysis, sensor instrumentation, telecommunications, and others. Many of these applications involve monitoring answers to continuous queries over data streams produced at physically distributed locations, and most previous approaches require streams to be transmitted to a single location for centralized processing. Unfortunately, the continual transmission of a large number of rapid data streams to a central location can be impractical or expensive. We study a useful class of queries that continuously report the k largest values obtained from distributed data streams (“top-k monitoring queries”), which are of particular interest because they can be used to reduce the overhead incurred while running other types of monitoring queries. We show that transmitting entire data streams is unnecessary to support these queries and present an alternative approach that reduces communication significantly. In our approach, arithmetic constraints are maintained at remote stream sources to ensure that the most recently provided top-k answer remains valid to within a userspecified error tolerance. Distributed communication is only necessary on occasion, when constraints are violated, and we show empirically through extensive simulation on real-world data that our approach reduces overall communication cost by an order of magnitude compared with alternatives that offer the same error guarantees. 1
Adaptive Filters for Continuous Queries over Distributed Data Streams.
We consider an environment where distributed  data sources continuously stream updates to a  centralized processor that monitors continuous  queries over the distributed data. Significant communication  overhead is incurred in the presence of  rapid update streams, and we propose a new technique  for reducing the overhead. Users register  continuous queries with precision requirements at  the central stream processor, which installs filters  at remote data sources. The filters adapt to changing  conditions to minimize stream rates while  guaranteeing that all continuous queries still receive  the updates necessary to provide answers of  adequate precision at all times. Our approach enables  applications to trade precision for communication  overhead at a fine granularity by individually  adjusting the precision constraints of continuous  queries over streams in a multi-query workload.


ScentTrails Integrating browsing and searching on the Web.
 
ScentTrails integrating browsing and searching on the Web.
 
Computing the Median with Uncertainty.

Visualizing Data with Bounded Uncertainty.
Visualization is a powerful way to facilitate data analysis,  but it is crucial that visualization systems explicitly  convey the presence, nature, and degree of uncertainty  to users. Otherwise, there is a danger that data will  be falsely interpreted, potentially leading to inaccurate  conclusions. A common method for denoting uncertainty  is to use error bars or similar techniques designed  to convey the degree of statistical uncertainty. While  uncertainty can often be modeled statistically, a second  form of uncertainty, bounded uncertainty, can also arise  that has very different properties than statistical uncertainty.
Best%2Deffort cache synchronization with source cooperation.
In environments where exact synchronization between source data objects and cached copies  is not achievable due to bandwidth or other resource constraints, stale (out-of-date) copies are  permitted. It is desirable to minimize the overall divergence between source objects and cached  copies by selectively refreshing modified objects. We call the online process of selecting which  objects to refresh in order to minimize divergence best-effort synchronization. In most approaches  to best-effort synchronization, the cache coordinates the process and selects objects  to refresh. In this paper, we propose a best-effort synchronization scheduling policy that exploits  cooperation between data sources and the cache. We also propose an implementation of  our policy that incurs low communication overhead even in environments with very large numbers  of sources. Our algorithm is adaptive to wide fluctuations in available resources and data  update rates. Through experimental simulation over synthetic and real-world data, we demonstrate  the effectiveness of our algorithm, and we quantify the significant decrease in divergence  achievable with source cooperation.
Adaptive Precision Setting for Cached Approximate Values.
Caching approximate values instead of exact values presents an opportunity for performance gains in exchange for decreased precision. To maximize the performance improvement, cached approximations must be of appropriate precision: approximations that are too precise easily become invalid, requiring frequent refreshing, while overly imprecise approximations are likely to be useless to applications, which must then bypass the cache. We present a parameterized algorithm for adjusting the precision of cached approximations adaptively to achieve the best performance as data values, precision requirements, or workload vary. We consider interval approximations to numeric values but our ideas can be extended to other kinds of data and approximations. Our algorithm strictly generalizes previous adaptive caching algorithms for exact copies: we can set parameters to require that all approximations be exact, in which case our algorithm dynamically chooses whether or not to cache each data value. We have implemented our algorithm and tested it on synthetic and real-world data. A number of experimental results are reported, showing the effectiveness of our algorithm at maximizing performance, and also showing that in the special case of exact caching our algorithm performs as well as previous algorithms. In cases where bounded imprecision is acceptable, our algorithm easily outperforms previous algorithms for exact caching. 1
DataSplash A Direct Manipulation Environment for Programming Semantic Zoom Visualizations of Tabular Data.

Getting Portals to Behave.

Computing the median with uncertainty.

Offering a Precision%2DPerformance Tradeoff for Aggregation Queries over Replicated Data.
Strict consistency of replicated data is infeasible or  not required by many distributed applications, so current  systems often permit stale replication,inwhich  cached copies of data values are allowed to become  out of date. Queries over cached data return an answer  quickly, but the stale answer may be unboundedly  imprecise. Alternatively, queries over remote  master data return a precise answer, but with potentially  poor performance. To bridge the gap between  these two extremes, we propose a new class of replication  systems called TRAPP (Tradeoff in Replication  Precision and Performance). TRAPP systems  give each user fine-grained control over the tradeoff  between precision and performance: Caches store  ranges that are guaranteed to bound the current data  values, instead of storing stale exact values. Users  supply a quantitative precision constraint along with  each query. To answer a query, TRAPP systems automatically  select a combination of locally cached  bounds and exact master data stored remotely to deliver  a bounded answer consisting of a range that is  no wider than the specified precision constraint, that  is guaranteed to contain the precise answer, and that  is computed as quickly as possible. This paper defines  the architecture of TRAPP replication systems  and covers some mechanics of caching data ranges. It  then focuses on queries with aggregation, presenting  optimization algorithms for answering queries with  precision constraints, and reporting on performance  experiments that demonstrate the fine-grained control  of the precision-performance tradeoff offered by  TRAPP systems.
Interactive data Analysis The Control Project.

DataSplash.
h---t---~---se2visu---liz---tion2is2---n2---re---2of2growing2import---n^TMe2---s d---t---~---se2systems2~e^TMome2l---rger2---nd2more2---^TM^TMessi~leF22h---t---fpl---sh is2---n2e---syEtoEuseD2integr---ted2environment2for2n---vig---tingD2^TMre---tingD ---nd2querying2visu---l2represent---tions2of2d---t---F22#e2will2demonstr---te the2three2m---in2^TMomponents2whi^TMh2m---ke2up2the2h---t---fpl---sh environmentX22---2n---vig---tion2systemD2---2dire^TMtEm---nipul---tion interf---^TMe2for2^TMre---ting2---nd2modifying2visu---liz---tionsD2---nd2---2dire^TMtE m---nipul---tion2visu---l2query2systemF  1. OVERVIEW  Database system performance as measured by either processing speed or the quantity of data that can be managed has grown by an order of magnitude in recent years, making increasingly sophisticated applications feasible on ever-larger datasets. However, database query languages have changed relatively little and are difficult for non-experts to use. The vast majority of database users are...
CONTROL Continuous Output and Navigation Technology with Refinement On%2DLine.
The CONTROL project at U.C. Berkeley has developed technologies to provide online behavior...
VIQING Visual Interactive Querying.

